package queue

type PriorityQueuelj struct {
	realSize int
	Item     []*Item
}

type Item struct {
	Value    interface{} // 元素值
	Priority int         // 优先级
}

func NewPriorityQueuelj(size int) *PriorityQueuelj {
	return &PriorityQueuelj{
		realSize: 0,
		Item:     make([]*Item, size),
	}
}

//offer = push，入队
func (queue *PriorityQueuelj) Offer(value interface{}) bool {
	// 优先级：default 0 ，最低
	return queue.OfferWithPriority(value, 0)
}

func (queue *PriorityQueuelj) OfferWithPriority(value interface{}, priority int) bool {
	// 判断队满
	if queue.realSize == len(queue.Item) {
		return false
	}
	queue.Item = append(queue.Item, &Item{
		Value:    value,
		Priority: priority,
	})
	queue.realSize++
	queue.shiftUp(queue.realSize)
	return false
}

//出队
func (queue *PriorityQueuelj) Poll() interface{} {
	if queue.realSize == 0 {
		return nil
	}
	item := queue.Item[0]

	return item
}

//弹出第一个队首元素（不删除）
func (queue *PriorityQueuelj) Peek() interface{} {
	if !queue.Empty() {
		return queue.Item[0].Value
	}
	return 0
}

//队列判空
func (queue *PriorityQueuelj) Empty() bool {
	// 没必要写 queue.item == nil，因为len(nil)==0
	// return queue.item == nil || len(queue.item) == 0
	return len(queue.Item) == 0
}

//获取真实队列长度
func (queue *PriorityQueuelj) GetRealSize() int {
	return queue.realSize
}

//获取最大队列长度
func (queue *PriorityQueuelj) GetMaxsize() int {
	return len(queue.Item)
}

//队列扩容
func (queue *PriorityQueuelj) ReSize() {
	// 2倍扩容
	tempSize := len(queue.Item)
	newItem := make([]*Item, tempSize*2)
	for i, _ := range queue.Item {
		newItem[i] = queue.Item[i]
	}
	queue.Item = newItem
}

//查找函数
func (queue *PriorityQueuelj) Search(value interface{}) bool {
	return false
}

// 优先队列调节
func (queue *PriorityQueuelj) shiftUp(index int) {
	if index > queue.realSize {
		return
	}
	for index > 0 {
		parentIndex := (index - 1) / 2 // 这一行不可以写在for循环外面
		if queue.Item[index].Priority > queue.Item[parentIndex].Priority {
			queue.Item[index], queue.Item[parentIndex] = queue.Item[parentIndex], queue.Item[index]
			index = parentIndex
		} else {
			return
		}
	}
}

func (queue *PriorityQueuelj) shiftDown(index int) {

}

func (queue *PriorityQueuelj) Method() {

}
